e-net (probability theory)

An $\varepsilon$ -net is any of several related concepts in mathematics, and has a particular meaning in probability theory where it is used in desription of the approximation of one probability distribution by another.

Theory

Let $P$ be a probability distribution over some set $X$ . An $\varepsilon$ -net for a class $H \subseteq 2^X$ of subsets of $X$ is any subset $S \subseteq X$ such that for any $h \in H$

$P(h) \ge \varepsilon \quad \Longrightarrow \quad S\cap h \neq \varnothing.$

Intuitively $S$ approximates the probability distribution.

A stronger notion is $\varepsilon$ -approximation. An $\varepsilon$ -approximation for class $H$ is a subset $S \subseteq X$ such that for any $h \in H$ it holds

$\left| P(h) - \frac{|S \cap h|}{|S|} \right| < \varepsilon .$